package com.fe.class03;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 反转双向链表
 * @Author sosuke :-)
 * @Date 2021/12/5 18:16
 */
public class Code02_ReverseDoubleLinkedList {

    public static class DoubleNode<T> {
        T data;
        DoubleNode<T> last = null;
        DoubleNode<T> next = null;

        public DoubleNode(T data) {
            this.data = data;
        }
    }

    /**
     * 使用两个指针完成双链表的反转
     * pre、head、next，三个指针是这个顺序，顺着双链表依次往后移动，直到head == null
     * next移动--->（head指针反转）---> pre移动--->head移动
     *
     * @return 返回反转后的头节点
     */
    public static DoubleNode<Integer> reverseDoubleLinkedList(DoubleNode<Integer> head) {
        DoubleNode<Integer> pre = null;
        DoubleNode<Integer> next = null;
        while (head != null) {
            next = head.next; // next移动
            head.next = pre; // 反转
            head.last = next;
            pre = head; // pre移动
            head = next; // head移动，移动后，下次要再判断head是否为null
        }
        return pre;
    }

    public static void main(String[] args) {
        int testTime = 1000;
        int maxSize = 10;
        int maxValue = 100;
        for (int i = 0; i < testTime; i++) {
            // 原地反转双向链表并检测
            DoubleNode<Integer> head = generateRandomDoubleLinkedList(maxSize, maxValue);
            List<DoubleNode<Integer>> originDoubleLinkedList = getOriginDoubleLinkedList(head);
            DoubleNode<Integer> reverseHead1 = reverseDoubleLinkedList(head); // 反转后，原head.next = null
            DoubleNode<Integer> reverseHead2 = testReverseDoubleLinkedList(originDoubleLinkedList);
            if (!doubleNodeEqual(reverseHead1, reverseHead2)) {
                System.out.println("Fuck!");
                printDoubleLinkedList(reverseHead1);
                printDoubleLinkedList(reverseHead2);
                return;
            }
        }
        System.out.println("Nice!");
        DoubleNode<Integer> head = generateRandomDoubleLinkedList(maxSize, maxValue);
        System.out.print(" origin===>");
        printDoubleLinkedList(head);
        DoubleNode<Integer> reverseHead = reverseDoubleLinkedList(head);
        System.out.print("reverse===>");
        printDoubleLinkedList(reverseHead);
    }

    public static boolean doubleNodeEqual(DoubleNode<Integer> head1, DoubleNode<Integer> head2) {
        DoubleNode<Integer> p1 = head1;
        DoubleNode<Integer> p2 = head2;
        // 正向比较
        while (p1 != null && p2 != null) {
            if (!p1.data.equals(p2.data)) {
                return false;
            }
            if (null == p1.next && null == p2.next) {
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 逆向比较
        while (p1 != null && p2 != null) {
            if (!p1.data.equals(p2.data)) {
                return false;
            }
            p1 = p1.last;
            p2 = p2.last;
        }
        return p1 == null && p2 == null;
    }

    /**
     * 使用list容器实现
     *
     * @param originLinkedList
     * @return
     */
    public static DoubleNode<Integer> testReverseDoubleLinkedList(List<DoubleNode<Integer>> originLinkedList) {
        if (null == originLinkedList || originLinkedList.size() == 0) return null;
        // 反转
        DoubleNode<Integer> pre = originLinkedList.get(0);
        pre.next = null;

        for (int i = 1; i < originLinkedList.size(); i++) {
            // 只用管当前节点和上一个节点的指向
            // cur.next-->cur.last-->pre.last-->移动pre
            DoubleNode<Integer> cur = originLinkedList.get(i);
            cur.next = pre;
            cur.last = null;
            pre.last = cur;
            pre = cur;
        }

        // 返回反转后的头节点
        return originLinkedList.get(originLinkedList.size() - 1);
    }

    /**
     * 逐个比较，判断反转结果是否正确
     *
     * @param originDoubleLinkedList
     * @param reverseNode
     * @return
     */
    // public static boolean checkReverseDoubleLinkedList(List<DoubleNode<Integer>> originDoubleLinkedList, DoubleNode<Integer> reverseNode) {
    //     DoubleNode<Integer> end = null;
    //     // 反向比较
    //     for (int i = originDoubleLinkedList.size() - 1; i >= 0; i--) {
    //         if (!originDoubleLinkedList.get(i).data.equals(reverseNode.data)) {
    //             return false;
    //         }
    //         end = reverseNode;
    //         reverseNode = reverseNode.next;
    //     }
    //     // 正向比较
    //     for (int i = 0; i < originDoubleLinkedList.size(); i++) {
    //         if (!originDoubleLinkedList.get(i).data.equals(end.data)) {
    //             return false;
    //         }
    //         end = end.last;
    //     }
    //     return true;
    // }

    /**
     * 把链表按顺序添加到容器中
     *
     * @param head
     * @return
     */
    public static List<DoubleNode<Integer>> getOriginDoubleLinkedList(DoubleNode<Integer> head) {
        List<DoubleNode<Integer>> list = new ArrayList<>();
        for (; head != null; head = head.next) {
            list.add(head);
        }
        return list;
    }

    /**
     * 随机生成双向链表
     *
     * @return
     */
    public static DoubleNode<Integer> generateRandomDoubleLinkedList(int maxSize, int maxValue) {
        // [0,maxSize]
        int size = (int) (Math.random() * (maxSize + 1));
        if (size == 0) return null;
        DoubleNode<Integer> head = new DoubleNode<>((int) (Math.random() * (maxValue + 1)));
        size--;
        DoubleNode<Integer> pre = head;
        for (int i = 0; i < size; i++) {
            DoubleNode<Integer> next = new DoubleNode<>((int) (Math.random() * (maxValue + 1)));
            pre.next = next;
            next.last = pre;
            pre = next;
        }
        return head;
    }

    /**
     * 打印双向链表
     *
     * @param head
     */
    public static void printDoubleLinkedList(DoubleNode<Integer> head) {
        if (null == head) {
            System.out.println("\"null\"");
            return;
        }
        DoubleNode<Integer> cur = head;
        while (null != cur) {
            System.out.print(cur.last == null ? "null" : "::"+cur.last.data);
            System.out.print("<---" + cur.data + "--->");
            System.out.print(cur.next == null ? "null" : cur.next.data);
            cur = cur.next;
        }
        System.out.println();
    }
}
